package ordena1;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
	public static final Random RND = new Random();

	private void swap(int[] array, int i, int j) {
		int tmp = array[i];
		array[i] = array[j];
		array[j] = tmp;
	}

	private int partition(int[] array, int begin, int end) {
		int index = begin + RND.nextInt(end - begin + 1);
		int pivot = array[index];
		swap(array, index, end);
		for (int i = index = begin; i < end; ++i) {
			if (array[i]<= (pivot)) {
				swap(array, index++, i);
			}
		}
		swap(array, index, end);
		return (index);
	}

	private void qsort(int[] array, int begin, int end) {
		if (end > begin) {
			int index = partition(array, begin, end);
			qsort(array, begin, index - 1);
			qsort(array, index + 1, end);
		}
	}

	public void sort(int[] array) {
		qsort(array, 0, array.length - 1);
	}

	// Exemplo de uso
	public static void main(String[] args) {

		// Ordenando Inteiros
		int[] l1 = { 5, 1024, 1, 88, 0, 1024 };
		System.out.println("l1  start:" + Arrays.toString(l1));
		QuickSort qs = new QuickSort();
		qs.sort(l1);
		System.out.println("l1 sorted:" + Arrays.toString(l1));

	}
}
